//
// Created by 123 on 2024/4/1.
//
/**
 * 快速排序
 *      两个指针，low 和 high 还有一个中轴数据，
 *          把大于中轴数据的放在 high的右边
 *          把小于中轴数据的放在 low的左边
 *      以此分治，即成
 *
 *      O(log n)
 */
#include <iostream>

using namespace std;

#define MaxSize 100

typedef struct Array {
    int data[MaxSize];
    int length;
} Array, *Arr;

Array *initArray(int arr[], int len);

void swap(int &a, int &b);


void quick_sort(Arr &arr);
//单次划分过程
int partition(Arr &arr, int low, int high);


int main() {
    int a[10]{49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
    Arr arr = initArray(a, 10);
    quick_sort(arr);
    for (int i = 0; i < arr->length; ++i) {
        cout << arr->data[i] << "    ";
    }
}

void quick_sort_ope(Arr &arr, int low, int high) {
    if (low < high) {
        int mid = partition(arr, low, high);
        quick_sort_ope(arr, mid + 1, high);
        quick_sort_ope(arr, low, mid - 1);
    }
}

void quick_sort(Arr &arr) {
//    下标从 1 开始，默认0有序
    quick_sort_ope(arr, 0, arr->length - 1);
}

int partition(Arr &arr, int low, int high) {
    //中轴数据，在low和high间任意位置都可以
    swap(arr->data[(low + high) / 2], arr->data[low]);
    int pivot = arr->data[low];
    while (low < high) {
        while (low < high && pivot <= arr->data[high])
            high--;
        arr->data[low] = arr->data[high];
        while (low < high && pivot >= arr->data[low])
            low++;
        arr->data[high] = arr->data[low];
    }
    arr->data[low] = pivot;
    return low;
}


Array *initArray(int arr[], int len) {
    Arr array = (Array *) malloc(sizeof(Array));
    for (int i = 0; i < len; ++i) {
        array->data[i] = arr[i];
    }
    array->length = len;
    return array;
}

void swap(int &a, int &b) {
    int turn = a;
    a = b;
    b = turn;
}